Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
УІ
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2016
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-32

Частина тексту файла

Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра прикладної математики КУРСОВА РОБОТА з курсу «Дискретна математика» на тему: «Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі» АНОТАЦІЯ У курсовій роботі розглянуто поняття синтаксичного аналізу, а саме, табличні методи синтаксичного аналізу контекстно-вільних граматик та алгоритм Ерлі. Дано загальні характеристику синтаксичного аналізу, його застосування, розглянуто поняття синтаксичного аналізатора та його видів. Описані табличні методи синтаксичного аналізу: алгоритм Кока-Янгера-Касамі та алгоритм Ерлі. Детально розглянуто алгоритм Ерлі, що дає можливість побудувати дерево розбору. Зокрема розглянуто два види реалізації цього алгоритму: за час 0(n3), де n – довжина вхідного ланцюжка, та за час 0(n2). Показана різниця цих видів реалізації. Наведено реалізацію алгоритму Ерлі – код програми, що будує дерево розбору вхідного ланцюжка на основі введеної граматики. SUMMARY In the coursework is examined the concept parsing, namely, tabular methods of parse for context-free grammars and algorithm Early. Given the general description of the parsing, its application, the notion parser and its species. Described tabular methods of parsing: algorithm Coc-Younger-Kasami and Earley algorithm. Is reviewed in detail Early algorithm which gives an algorithm that makes it possible to build a tree parsing. Two particular types implement this algorithm: at time 0(n3), where n - the length of the input string, and at time 0(n2). Shown difference of these types of realization. Given an Early algorithm implementation - source code that builds the parse tree of the input string based on the entered grammar. ЗМІСТ ВСТУП 5 СИНТАКСИЧНИЙ АНАЛІЗ 6 МЕТОДИ ТАБЛИЧНОГО СИНТАКСИЧНОГО АНАЛІЗУ 9 АЛГОРИТМ ЕРЛІ 10 ВИСНОВОК 22 ДОДАТОК 23 СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 42 ВСТУП Алгоритм Ерлі являє собою низхідний алгоритм табличного синтаксичного аналізу, тобто побудову дерева розбору здійснюється зверху вниз. Хоча, як і в алгоритмі Кока-Янгера-Касамі, верхня оцінка на часову складність алгоритму являє собою куб по довжині слова, на практиці константа в алгоритмі Ерлі значно нижча. Крім того, для однозначних граматик доведена квадратична верхня оцінка на час роботи алгоритму, а для багатьох граматик в реальності складність виявляється лінійною. Через відносну простоту алгоритму це дозволяє використовувати його в окремих практичних додатках (хоча в цілому LR- і GLR-алгоритми розбору є значно більш популярними). Алгоритм Ерлі отримує на вхід контекстно-вільну граматику G=(N,
Антиботан аватар за замовчуванням

13.05.2017 14:05

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини